package com.leetcode.partition1;

import com.leetcode.common.ListNode;

/**
 * @author `RKC`
 * @date 2021/10/21 8:50
 */
public class LC82删除排序链表中的重复元素2 {

    public static ListNode deleteDuplicates(ListNode head) {
        return doublePointer(head);
    }

    public static void main(String[] args) {
//        ListNode head = new ListNode(2, new ListNode(2, new ListNode(3, new ListNode(3,
//                new ListNode(4, new ListNode(5, new ListNode(6)))))));
        ListNode head = new ListNode(1, new ListNode(1, new ListNode(1)));
        head = deleteDuplicates(head);
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + "  ");
            cur = cur.next;
        }
    }

    private static ListNode doublePointer(ListNode head) {
        //前面接入两个虚拟节点，目的是为了不做特殊处理
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE, new ListNode(Integer.MIN_VALUE + 1, head));
        ListNode prev = dummyHead, left = dummyHead.next, right = dummyHead.next.next;

        //prev指向当前节点的前一个节点，根据right指针判断是否重复，如果right的值和left相等，移动right指针，直到right不等于left，
        //此时将prev的next指向right，并将prev和left指向right，right向后移动
        while (right != null) {
            boolean flag = false;
            while (right != null && left.val == right.val) {
                right = right.next;
                flag = true;
            }
            if (flag) {
                //如果有重复节点，需要将prev的下一个指向当前没有重复的节点，也就是right，同时left和right需要向后移动
                prev.next = right;
                left = right;
                if (right != null) right = right.next;
                continue;
            }
            //没有重复节点，正常向后移动
            prev = left;
            left = right;
            right = right.next;
        }
        return dummyHead.next.next;
    }
}
